/**
 * @(#) MergSort.java Mar 23, 2010 2:14:16 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package array;

/**
 * Class <code>MergSort</code>
 * 
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Mar 23, 2010 2:14:16 PM
 * 
 */
public class MergSort
{

	private static int[] mergeSort(int[] data, int left, int right)
	{
		if(data == null)
			return null;
		if (data.length < 2)
			return data;
		if (left < right)
		{
			int middle = left + ((right - left) >>1);
			mergeSort(data, left, middle);
			mergeSort(data, middle + 1, right);
			merge(data, left, middle + 1, right);
		}
		return data;
	}

	private static void merge(int[] data, int left, int middle, int right)
	{

		int[] tmpArray = new int[data.length];
		int leftEnd = middle - 1;
		int tmpPos = left;
		int numElements = right - left + 1;

		while (left <= leftEnd && middle <= right)
		{
			if (data[left] < (data[middle]))
				tmpArray[tmpPos++] = data[left++];
			else
				tmpArray[tmpPos++] = data[middle++];
		}

		while (left <= leftEnd)
			tmpArray[tmpPos++] = data[left++];

		while (middle <= right)
			tmpArray[tmpPos++] = data[middle++];

		for (int i = 0; i < numElements; i++, right--)
			data[right] = tmpArray[right];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		int[] data =
		{ 2, 3, 1, 5, 4 };
		MergSort.mergeSort(data, 0, 4);
		System.out.println("");
	}

}
